package com.LeeCode;

/**
 * 烹饪料理
 */

public class CodeLCP051 {
    public static void main(String[] args) {
        int[] materials = {3, 2, 4, 1, 2};
        int[][] cookbooks = {
                {1, 1, 0, 1, 2},
                {2, 1, 4, 0, 0},
                {3, 2, 4, 1, 0}
        };
        int[][] attribute = {
                {3, 2},
                {2, 4},
                {7, 6}
        };
        int limit = 5;

        System.out.println(new CodeLCP051().perfectMenu(materials, cookbooks, attribute, limit));
    }

    private int ans = -1;
    private boolean[] cooked;

    public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
        cooked = new boolean[cookbooks.length];
        backtrace(materials, cookbooks, attribute, limit, 0);
        return ans;
    }

    private void backtrace(int[] materials, int[][] cookbooks, int[][] attribute, int limit, int delicious) {
        if (limit <= 0) {
            ans = Math.max(ans, delicious);
        }

        for (int index = 0; index < cookbooks.length; index++) {
            int[] cookbook = cookbooks[index];
            // 若没做过，且材料满足制作要求
            if (!cooked[index] && check(materials, cookbook)) {
                // 减对应的材料
                for (int i = 0; i < materials.length; i++) {
                    materials[i] -= cookbook[i];
                }
                // 标记为已制作
                cooked[index] = true;
                backtrace(materials, cookbooks, attribute, limit - attribute[index][1], delicious + attribute[index][0]);
                // 回溯，撤销操作
                for (int i = 0; i < materials.length; i++) {
                    materials[i] += cookbook[i];
                }
                cooked[index] = false;
            }
        }

    }

    // 检查当前材料能否制作该料理
    private boolean check(int[] materials, int[] cookbook) {
        for (int i = 0; i < materials.length; i++) {
            if (materials[i] < cookbook[i])
                return false;
        }
        return true;
    }
}
